package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode_day8 {

	/**
	 * ？Given a collection of numbers that might contain duplicates, 
	 * return all possible unique permutations.
	 * 
	 * For example,
	 * [1,1,2] have the following unique permutations:
	 * [1,1,2], [1,2,1], and [2,1,1].
	 * 
	 * 
	 * @param a
	 */
	public static List<int[]> permu2(int a[]){
		if(a == null || a.length == 0) return null;
		
		List<int[]> ress = new ArrayList<int[]>();
		ress.add(a);
		if(a.length == 1) return ress;
		
		permutations2(a.length, 0, ress);
		return ress;
	}
	public static void permutations2(int length, int fixedPos, List<int[]> ress){
		if(fixedPos == length-1) return;
		int oldLength = ress.size();
		for(int i = 0 ; i < oldLength ; i++){
			int[] res = ress.get(i);
			for(int j = fixedPos+1 ; j < length ; j++){
				if(res[fixedPos] != res[j]){
					int[] newres = Arrays.copyOf(res, length);
					newres[fixedPos] = newres[fixedPos] ^ newres[j];
					newres[j] = newres[fixedPos] ^ newres[j];
					newres[fixedPos] = newres[fixedPos] ^ newres[j];
					ress.add(newres);
				}
			}
		}
		permutations2(length, fixedPos+1, ress);
	}
	/**
	 * An other approach for question permutations I.
	 * 
	 * Analysis:
	 * The basic idea is that swap two numbers of the array.
	 * For the length of n, the permutations can be generated by:
	 * 1) swap the 1st element with all the elements, including itself
	 * 2) Then the 1st element is fixed, go to next element
	 * 3) Until the last element is fixed.
	 * @param a
	 */
	public static List<int[]> permu1(int[] a){
		List<int[]> ress = new ArrayList<int[]>();
		ress.add(a);
		permutations1(a.length, 0, ress);
		return ress;
	}
	
	public static void permutations1(int length, int fixedPos, List<int[]> ress){
		if(fixedPos == length-1) return;
		//swap the fixed position value with any other values
		int oldLength = ress.size();
		for(int j = 0 ; j < oldLength ; j++){
			int[] res = ress.get(j);
			for(int i = fixedPos+1 ; i < length ; i++){
				//swap res[i] and res[fixedPos]
				int[] newres = Arrays.copyOf(res, res.length);
				newres[fixedPos] = newres[fixedPos] ^ newres[i];
				newres[i] = newres[fixedPos] ^ newres[i];
				newres[fixedPos] = newres[fixedPos] ^ newres[i];
				ress.add(newres);
			}
		}
		permutations1(length, fixedPos+1, ress);
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		List<int[]> ress = permu1(new int[]{1,2,3});
		for(int[] res : ress){
			for(int i : res)
				System.out.print(i+" ");
			System.out.println();
		}
		
		ress = permu2(new int[]{1,2,2});
		for(int[] res : ress){
			for(int i : res)
				System.out.print(i+" ");
			System.out.println();
		}
	}

}
